package leetcode_algorithm.First_Missing_Positive;

/**

Given an unsorted integer array, find the first missing positive integer.

        For example,
        Given [1,2,0] return 3,
        and [3,4,-1,1] return 2.

        Your algorithm should run in O(n) time and uses constant space.

*/

public class Solution {


    public static void main(String[] args) {
        System.out.println(new Solution().firstMissingPositive(new int[]{1 ,2 , 0}));
        System.out.println(new Solution().firstMissingPositive(new int[]{3 , 4 , -1 , 1}));
        System.out.println(new Solution().firstMissingPositive(new int[]{7 , 8 , 1 , 2}));
    }

    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if(nums[i] == i+1 || nums[i] <= 0 || nums[i] > nums.length) i++;
            else if(nums[nums[i] - 1] != nums[i]) swap(nums , i , nums[i] - 1);
            else i++;
        }
        i = 0;
        while(i < nums.length && nums[i] == i+1) i++;
        return i+1;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }


}
